#include <iostream> 
using namespace std;

void printArr(int *arrP,int n)
{ for (int i = 0; i < n; ++i) printf("%d ",*arrP++);
    printf("\n"); }

int main()
{
	int arr[]={6,5,4,3,2,1,3,9,4,2,5,7,8};
	int l = sizeof(arr)/sizeof(int);
	int step = l/2;
	while(step>0)
	{
        for (int i = 0; i < l; i+=step) {
            int j = i;
            int value = arr[j+step];
            while(j>=0 && value<arr[j])
            {
                arr[j+step] = arr[j];
                j-=step;
            }
            arr[j+step]=value;
        }
        step/=2;
	}
	printArr(arr,l);
}
